import heapq
class Solution(object):
    def minimumDifference(self, nums):
        n = len(nums)
        left_ans = [0] * n
        t = n // 3
        left_st = nums[: t]
        now_sum = sum(left_st)
        left_st = [-num for num in left_st]
        heapq.heapify(left_st)
        left_ans[t - 1] = now_sum
        for i in range(t, 2 * t):
            if nums[i] < - left_st[0]:
                now_sum += (nums[i] + left_st[0])
                heapq.heapreplace(left_st, - nums[i])
                left_ans[i] = now_sum
            else:
                left_ans[i] = left_ans[i - 1]
        right_ans = [0] * n
        right_st = nums[2 * t:]
        now_sum = sum(right_st)
        right_ans[2 * t] = now_sum
        right_st = [num for num in right_st]
        heapq.heapify(right_st)
        for i in range(2 * t - 1, t - 1, -1):
            if nums[i] > right_st[0]:
                now_sum += nums[i] - right_st[0]
                heapq.heapreplace(right_st, nums[i])
                right_ans[i] = now_sum
            else:
                right_ans[i] = right_ans[i + 1]
        min_num = float('inf')
        for i in range(t - 1, 2 * t):
            min_num = min(min_num, left_ans[i] - right_ans[i + 1])
        return min_num

data = Solution()
nums = [7,9,5,8,1,3]
print(data.minimumDifference(nums))